<?php
/**
 * User: helloJiu
 * Date: 2021/11/5
 * Time: 15:32
 */

namespace App\Algorithm\DP;


class CoinChangeIII
{
    /**
     * @param Integer[] $coins
     * @param Integer $amount
     * @return Integer
     */
    function coinChange($coins, $amount)
    {

        /*
         给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

        计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

        你可以认为每种硬币的数量是无限的。

        示例 1：

        输入：coins = [1, 2, 5], amount = 11
        输出：3
        解释：11 = 5 + 5 + 1

        来源：力扣（LeetCode）
        链接：https://leetcode-cn.com/problems/coin-change
        著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
         */

        // $dp[$i]: 凑够$i需要的最少硬币个数
        $dp = [];
        for ($i = 0; $i <= $amount; $i++) {
            $dp[$i] = PHP_INT_MAX;
        }

        // 凑够0不需要硬币
        // $dp[5-5] + 1 : 用5分硬币凑够5分需要一枚
        $dp[0] = 0;

        foreach ($coins as $coin) {
            for ($i = 1; $i <= $amount; $i++) {
                if ($i >= $coin) {
                    $dp[$i] = min($dp[$i], $dp[$i - $coin] + 1);
                }
            }
        }

        return $dp[$amount] == PHP_INT_MAX ? -1 : $dp[$amount];


    }
}